#include<iostream>
#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        s1 = '-' + s1;
        s2 = '-' + s2;
        s3 = '-' + s3;
        int len1 = s1.size();
        int len2 = s2.size();
        if (len1 + len2 - 1 != s3.size()) return false;
        vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));
        dp[0][0] = true;
        for (int i = 1; i < len1; i++)
            if (s1[i] == s3[i]) dp[i][0] = true;
            else break;
        for (int j = 1; j < len2; j++)
            if (s2[j] == s3[j]) dp[0][j] = true;
            else break;
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (s1[i] == s3[i + j] && dp[i - 1][j]) dp[i][j] = true;
                else if (s2[j] == s3[i + j] && dp[i][j - 1]) dp[i][j] = true;
            }
        }
        return dp[len1 - 1][len2 - 1];
    }
};


class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        s1 = '-' + s1;
        s2 = '-' + s2;
        int len1 = s1.size();
        int len2 = s2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 2 * s1[i]);
                }
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        long long sum = 0;
        for (int i = 1; i < len1; i++)
            sum += s1[i];
        for (int j = 1; j < len2; j++)
            sum += s2[j];
        return sum - dp[len1 - 1][len2 - 1];
    }
};


class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
};


class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        int maxd = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                maxd = max(maxd, dp[i][j]);
            }
        }
        return maxd;
    }
};

